package Graph.graphWithNoweight.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/10 10:14
 * @Version 1.0
 */
public class leetCode1091 {
    private int[][] dirs = {{-1,0},{-1,1},{0,1},{1,1},
                            {1,0},{1,-1},{0,-1},{1,1}};
    private int R,C;
    public int shortestPathBinaryMatrix(int[][] grid){
        int R = grid.length;
        int C = grid[0].length;

        boolean[][] visited = new boolean[R][C];
        // 这个dis 二维数组是统计步数的。。即[0][0] 到[i][j] 的步数
        int[][] dis = new int[R][C];
        if(grid[0][0] == 1){
            return -1;
        }
        if(R==1 && C==1){
            return 1;
        }
        //BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0][0] = true;
        dis[0][0] = 1;

        while (!queue.isEmpty()){
            int cur = queue.remove();
            int curx = cur/C ;
            int cury = cur%C;
            //构建某个点 的adj();
            for(int d=0;d<8;d++){
                int nextx = curx+dirs[d][0];
                int nexty = cury+dirs[d][1];
                if (inArea(nextx,nexty) && !visited[nextx][nexty] && grid[nextx][nexty]==0) {
                    queue.add(nextx*C +nexty);
                    visited[nextx][nexty] = true;
                    //在原来的步骤上+1
                    dis[nextx][nexty] = dis[curx][cury] + 1;
                    if(nextx == R-1 && nexty == C-1){
                        return dis[nextx][nexty];
                    }
                }
            }
        }

        return 0;
    }

    private boolean inArea(int x,int y){
        return x>=0 && x<R || y>=0 && y<C;
    }
}
